using namespace std;
#include<iostream>
#include<vector>

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        vector<int>::iterator it = nums.begin();
        vector<int>::iterator next = it + 1;
        while (next != nums.end())
        {
            if (*next == *it)
            {
                nums.erase(next);
                next = it + 1;
            }
            else
            {
                it++;
                next = it + 1;
            }
        }

        return nums.size();
    }
};


class Solution {
public:

    int f(int num, int target)
    {
        if (num == 1) return 0;
        int x = f(num - 1, target);
        return (x + target) % num;
    }
    int iceBreakingGame(int num, int target) {
        return f(num, target);
    }
};


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !k) return head;
        ListNode* tail = head;
        int size = 1;
        while (tail->next != nullptr)
        {
            size++;
            tail = tail->next;
        }

        int n = size - k % size - 1;

        ListNode* cur = head;
        for (int i = 0; i < n; i++)
        {
            cur = cur->next;
        }
        tail->next = head;
        head = cur->next;
        cur->next = nullptr;
        return head;
    }
};


class Solution {
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        dfs(A, B, C, A.size());
    }

    void dfs(vector<int>& A, vector<int>& B, vector<int>& C, int n)
    {
        if (n == 1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }

        dfs(A, C, B, n - 1);
        C.push_back(A.back());
        A.pop_back();
        dfs(B, A, C, n - 1);
    }
};